﻿namespace ConsoleApp.Tree;

public static class TreeTraversal
{
    // 深度优先遍历（前序）
    public static IEnumerable<T> DepthFirst<T>(
        this TreeNode<T> root)
    {
        var stack = new Stack<TreeNode<T>>();
        stack.Push(root);
        while (stack.Count > 0)
        {
            var current = stack.Pop();
            yield return current.Current;
            foreach (var child in current.Children.Reverse())
                stack.Push(child);
        }
    }
 
    // 广度优先遍历
    public static IEnumerable<T> BreadthFirst<T>(
        this TreeNode<T> root)
    {
        var queue = new Queue<TreeNode<T>>();
        queue.Enqueue(root);
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            yield return current.Current;
            foreach (var child in current.Children)
                queue.Enqueue(child);
        }
    }
}